package first.codeTop.meituan;


public class Leetcode53 {
    // 最大子序和
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

    // df[i] 表示以i位结尾的最大子序列的和
    public static int maxSubArray(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = nums[0];
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (result[i-1] < 0) {
                result[i] = nums[i];
            } else {
                result[i] = result[i-1]+nums[i];
            }
            max = Math.max(max, result[i]);
        }
        return max;
    }
}
